package benchmark.SFT;

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import org.sat4j.specs.TimeoutException;
import theory.characters.CharConstant;
import theory.characters.CharFunc;
import theory.characters.CharOffset;
import theory.characters.CharPred;
import theory.characters.StdCharPred;
import theory.intervals.UnaryCharIntervalSolver;
import transducers.sft.SFT;
import transducers.sft.SFTInputMove;
import transducers.sft.SFTMove;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

/* Browser and plugin fingerprinting code found in JavaScript malware:

var quicktime_plugin = "0", adobe_plugin = "00", flash_plugin = "0", video_plugin = "00";

function get_version(s, max_offset) {
    //...
}

for (var i = 0; i < navigator.plugins.length; i++) {
    var plugin_name = navigator.plugins[i].name;
    if (quicktime_plugin == 0 && plugin_name.indexOf("Quicktime") != 1) {
        var helper = parseInt(plugin_name.replace(/\D/g, ""));
        if (helper > 0) // not base 16
            quicktime_plugin = helper.toString(10);
    }
    if (adobe_plugin == "00" && plugin_name.indexOf("Adobe Acrobat") != -1) {
        plugin_name = navigator.plugins[i].description;
        if (plugin_name.indexOf(" 5") != -1)
            adobe_plugin = "05";
        else if(plugin_name.indexOf(" 6") != -1)
            adobe_plugin = "06";
        else if(plugin_name.indexOf(" 7") != -1)
            adobe_plugin = "07";
        else
            adobe_plugin = "01";
    } else {
        if (flash_plugin == "0" && plugin_name.indexOf("Shockwave Flash") != -1)
            flash_plugin = get_ver(navigator.plugins[i].description, 4);
        else if (window.navigator.javaEnabled && java_plugin == 0 && plugin_name.indexOf("Java") != -1)
            java_plugin = get_ver(navigator.plugins[i].description, 4);
    }
}

if (navigator.mimeTypes["video/x-ms-wmv"].enabledPlugin)
    video_plugin = "01";

while (quicktime_plugin.length < 8)
    quicktime_plugin = "0" + quicktime_plugin;
while (flash_plugin.length < 8)
    flash_plugin = "0" + flash_plugin;
while (java_plugin.length < 8)
    java_plugin = "0" + java_plugin;

var fingerprint = "Q" + quicktime_plugin + "9" + video_plugin + "8" + adobe_plugin + "F" + flash_plugin + "J"+java_plugin;

var system_language;
if (!(system_language = navigator.systemLanguage))
    if (!(system_language = navigator.userLanguage))
        if (!(system_language = navigator.browserLanguage))
            system_language = navigator.language;
if (system_language) {
    system_language = system_language.substr(0,10);
    var language = "";
    for(var i = 0; i < system_language.length; i++) {
        var l = system_language.charCodeAt(i).toString(16);
        if (l < 2)
            language += "0";
        language += l;
    }
    while (language.length < 20)
        language += "00";
    fingerprint += "L" + language;
}

// send out a request that depends on generated fingerprint
fetch_exploit(fingerprint);
*/

/**
* generate fingerprint based on the version of Quicktime
 * It is an implementation of the example on page 10 of a paper called Symbolic Finite State Transducers: Algorithms And
 * Applications
 * You could use JUnit to test method GetTagsBySFT or just use normal way to run the main method
 */
public class MalwareFingerprintingDecode {
    private static UnaryCharIntervalSolver ba = new UnaryCharIntervalSolver();
    private static SFT<CharPred, CharFunc, Character> QuicktimeSplitter;
    private static SFT<CharPred, CharFunc, Character> QuicktimeMerger;
    private static SFT<CharPred, CharFunc, Character> QuicktimePadder;
    private static SFT<CharPred, CharFunc, Character> composed = null;

    /**
     * Figure 10 on Page 10
     */
    private static SFT<CharPred, CharFunc, Character> MkQuicktimeSplitter() throws TimeoutException {
        List<SFTMove<CharPred, CharFunc, Character>> transitions = new LinkedList<SFTMove<CharPred, CharFunc, Character>>();
        char[] Quicktime = "Quicktime".toCharArray();
        
        List<CharFunc> output1_2 = new ArrayList<CharFunc>();
        output1_2.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(1, 2, new CharPred('0'), output1_2));

        List<CharFunc> output2_2 = new ArrayList<CharFunc>();
        output2_2.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(2, 2, new CharPred('0'), output2_2));

        List<CharFunc> output2_3 = new ArrayList<CharFunc>();
        output2_3.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(2, 3, new CharPred('#'), output2_3));


        for (int i = 3; i <= 11; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, 3, ba.MkNot(new CharPred(Quicktime[i - 3])), output));
        }

        for (int i = 3; i <= 11; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred(Quicktime[i - 3]), output));
        }

        List<CharFunc> output2_13 = new ArrayList<CharFunc>();
        output2_13.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(2, 13, new CharPred('1', '9'), output2_13));

        List<CharFunc> output1_13 = new ArrayList<CharFunc>();
        output1_13.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(1, 13, new CharPred('1', '9'), output1_13));

        List<CharFunc> output13_13 = new ArrayList<CharFunc>();
        output13_13.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(13, 13, new CharPred('1', '9'), output13_13));

        List<CharFunc> output13_14 = new ArrayList<CharFunc>();
        output13_14.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(13, 14, new CharPred('#'), output13_14));

        List<CharFunc> output14_14 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(14, 14, StdCharPred.TRUE, output14_14));

        List<CharFunc> output1_15 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(1, 15, new CharPred('0'), output1_15));

        List<CharFunc> output15_15 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(15, 15, new CharPred('0'), output15_15));

        List<CharFunc> output15_16 = new ArrayList<CharFunc>();
        output15_16.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(15, 16, new CharPred('#'), output15_16));

        for (int i = 16; i <= 24; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, 16,
                    ba.MkAnd(ba.MkNot(new CharPred('0', '9')), ba.MkNot(new CharPred(Quicktime[i - 16]))) , output));
        }

        for (int i = 16; i <= 24; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, 16, new CharPred('0', '9') , output));
        }

        for (int i = 16; i <= 24; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred(Quicktime[i - 16]) , output));
        }

        List<CharFunc> output25_25 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(25, 25, ba.MkNot(new CharPred('0', '9')), output25_25));

        output25_25 = new ArrayList<CharFunc>();
        output25_25.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(25, 25, new CharPred('0', '9'), output25_25));

        Map<Integer, Set<List<Character>>> finStatesAndTails = new HashMap<Integer, Set<List<Character>>>();
        for (int i = 3; i <= 11; i++)
            finStatesAndTails.put(i, new HashSet<List<Character>>());
        finStatesAndTails.put(14, new HashSet<List<Character>>());
        finStatesAndTails.put(25, new HashSet<List<Character>>());

        return SFT.MkSFT(transitions, 1, finStatesAndTails, ba);
    }


    /**
     * since the output of QuicktimeSplitter is in decimal base, we only need to wipe out '#'
     */
    private static SFT<CharPred, CharFunc, Character> MkQuicktimeMerger() throws TimeoutException {
        List<SFTMove<CharPred, CharFunc, Character>> transitions = new LinkedList<SFTMove<CharPred, CharFunc, Character>>();

        List<CharFunc> output01 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(0, 1, new CharPred('#'), output01));

        List<CharFunc> output12 = new ArrayList<CharFunc>();
        output12.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(1, 2, new CharPred('0', '9'), output12));

        List<CharFunc> output22 = new ArrayList<CharFunc>();
        output22.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(2, 2, new CharPred('0', '9'), output22));

        List<CharFunc> output03 = new ArrayList<CharFunc>();
        output03.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(0, 3, new CharPred('0', '9'), output03));

        List<CharFunc> output33 = new ArrayList<CharFunc>();
        output33.add(CharOffset.IDENTITY);
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(3, 3, new CharPred('0', '9'), output33));

        List<CharFunc> output34 = new ArrayList<CharFunc>();
        transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(3, 4, new CharPred('#'), output34));

        Map<Integer, Set<List<Character>>> finStatesAndTails = new HashMap<Integer, Set<List<Character>>>();
        finStatesAndTails.put(2, new HashSet<List<Character>>());
        finStatesAndTails.put(4, new HashSet<List<Character>>());

        return SFT.MkSFT(transitions, 0, finStatesAndTails, ba);
    }

    /**
     * pad the string with 0 in front of it if its length is smaller than 8
     */
    private static SFT<CharPred, CharFunc, Character> MkQuicktimePadder() throws TimeoutException {
        List<SFTMove<CharPred, CharFunc, Character>> transitions = new LinkedList<SFTMove<CharPred, CharFunc, Character>>();

        for (int i = 1; i <= 7; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 9; i <= 14; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 16; i <= 20; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 22; i <= 25; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 27; i <= 29; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 31; i <= 32; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        for (int i = 34; i <= 34; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(i, i + 1, new CharPred('0', '9'), output));
        }

        int[] toStates = {1, 9, 16, 22, 27, 31, 34, 36};
        for (int i = 0; i < toStates.length; i++) {
            List<CharFunc> output = new ArrayList<CharFunc>();
            for (int j = 0; j < i; j++)
                output.add(new CharConstant('0'));
            output.add(CharOffset.IDENTITY);
            transitions.add(new SFTInputMove<CharPred, CharFunc, Character>(0, toStates[i], new CharPred('0', '9'), output));
        }

        Map<Integer, Set<List<Character>>> finStatesAndTails = new HashMap<Integer, Set<List<Character>>>();
        finStatesAndTails.put(8, new HashSet<List<Character>>());
        finStatesAndTails.put(15, new HashSet<List<Character>>());
        finStatesAndTails.put(21, new HashSet<List<Character>>());
        finStatesAndTails.put(26, new HashSet<List<Character>>());
        finStatesAndTails.put(30, new HashSet<List<Character>>());
        finStatesAndTails.put(33, new HashSet<List<Character>>());
        finStatesAndTails.put(35, new HashSet<List<Character>>());
        finStatesAndTails.put(36, new HashSet<List<Character>>());
        return SFT.MkSFT(transitions, 0, finStatesAndTails, ba);
    }

    public static String splitBySFT(String input) throws TimeoutException {
        List<Character> listOfInput = stringToListOfCharacter(input);
        List<Character> output = QuicktimeSplitter.outputOn(listOfInput, ba);
        if (output != null)
            return ba.stringOfList(output);
        else
            return null;
    }

    public static String mergeBySFT(String input) throws TimeoutException {
        List<Character> listOfInput = stringToListOfCharacter(input);
        List<Character> output = QuicktimeMerger.outputOn(listOfInput, ba);
        if (output != null)
            return ba.stringOfList(output);
        else
            return null;
    }

    public static String padBySFT(String input) throws TimeoutException {
        List<Character> listOfInput = stringToListOfCharacter(input);
        List<Character> output = QuicktimePadder.outputOn(listOfInput, ba);
        if (output != null)
            return ba.stringOfList(output);
        else
            return null;
    }

    public static String overallBySFT(String input) throws TimeoutException {
        if (composed == null)
            composed = SFT.compose(QuicktimeSplitter, QuicktimeMerger, ba).composeWith(QuicktimePadder, ba);

        List<Character> listOfInput = stringToListOfCharacter(input);
        List<Character> output = composed.outputOn(listOfInput, ba);
        if (output != null)
            return ba.stringOfList(output);
        else
            return null;
    }

    /**
     * convert a string into a list of characters
     * @param input a string
     * @return a list of class Character
     */
    private static List<Character> stringToListOfCharacter(String input) {
        List<Character> output = new ArrayList<Character>();
        for (char character: input.toCharArray())
            output.add(character);
        return output;
    }

    public static void main(String args[]) throws TimeoutException {

        System.out.println(splitBySFT("00#Quicktime7.6.9"));
        System.out.println(splitBySFT("769#Quicktime7.6.9"));
        System.out.println(splitBySFT("769#Acrobat9.4.5.236"));
        System.out.print('\n');

        System.out.println(mergeBySFT("#769"));
        System.out.print('\n');

        System.out.println(padBySFT("769"));
        System.out.print('\n');

        System.out.println(overallBySFT("00#Quicktime7.6.9"));
        System.out.println(overallBySFT("769#Quicktime7.6.9"));
        System.out.println(overallBySFT("769#Acrobat9.4.5.236"));
    }

    @Test
    public void test() throws Exception {
        QuicktimeSplitter = MkQuicktimeSplitter();
        QuicktimeMerger = MkQuicktimeMerger();
        QuicktimePadder = MkQuicktimePadder();

        assertEquals("#769", splitBySFT("0#Quicktime7.6.9"));
        assertEquals("#769", splitBySFT("00#Quicktime7.6.9"));
        assertEquals("#769", splitBySFT("000000#Quicktime7.6.9"));
        assertEquals("769#", splitBySFT("769#Quicktime7.6.9"));
        assertEquals("0769#", splitBySFT("0769#Quicktime7.6.9"));
        assertEquals("000769#", splitBySFT("000769#Quicktime7.6.9"));
        assertEquals("769#", splitBySFT("769#Quickt7.6.9"));
        assertEquals("769#", splitBySFT("769#Flash7.6.9"));
        assertEquals("769#", splitBySFT("769#"));
        assertEquals(null, splitBySFT("#Quicktime7.6.9")); // invalid input
        assertEquals(null, splitBySFT("769"));
        assertEquals(null, splitBySFT("Quick#"));
        assertEquals(null, splitBySFT("123Quick456#"));

        assertEquals("769", mergeBySFT("769#"));
        assertEquals("769", mergeBySFT("#769"));
        assertEquals(null, mergeBySFT("#"));
        assertEquals(null, mergeBySFT("abc"));

        assertEquals("00000000", padBySFT("0"));
        assertEquals("00000007", padBySFT("7"));
        assertEquals("00000012", padBySFT("12"));
        assertEquals("00000123", padBySFT("123"));
        assertEquals("00001234", padBySFT("1234"));
        assertEquals("00012345", padBySFT("12345"));
        assertEquals("00123456", padBySFT("123456"));
        assertEquals("01234567", padBySFT("1234567"));
        assertEquals("12345678", padBySFT("12345678"));
        assertEquals("33333333", padBySFT("33333333"));
        assertEquals(null, padBySFT("")); // no input
        assertEquals(null, padBySFT("a")); // non digits (alphabet)
        assertEquals(null, padBySFT("090abd12")); // non digits
        assertEquals(null, padBySFT("123456789")); // too many digits

        assertEquals("00000769", overallBySFT("00#Quicktime7.6.9"));
        assertEquals("00000769", overallBySFT("769#Quicktime7.6.9"));
        assertEquals("00000769", overallBySFT("769#Acrobat9.4.5.236"));
        assertEquals("00000000", overallBySFT("00#Acrobat9.4.5.236"));
        assertEquals(null, overallBySFT("#Quicktime7.6.9")); // invalid input
        assertEquals(null, overallBySFT("769"));
        assertEquals(null, overallBySFT("Quick#"));
        assertEquals(null, overallBySFT("123Quick456#"));

        // use 2 different ways to compose 3 SFTs
        SFT<CharPred, CharFunc, Character> composed1 = SFT.compose(QuicktimeSplitter, QuicktimeMerger, ba).composeWith(QuicktimePadder, ba);
        SFT<CharPred, CharFunc, Character> composed2 = SFT.compose(QuicktimeSplitter, QuicktimeMerger.composeWith(QuicktimePadder, ba), ba);
        assertTrue(SFT.decide1equality(composed1, composed2, ba));
    }
}
